'''
利用1+3+5+...+2n-1 = n²
'''


'''
二分查找
'''
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 2:
            return True

        left, right = 2, num // 2

        while left <= right:
            x = left + (right - left) // 2
            guess_squared = x * x
            if guess_squared == num:
                return True
            if guess_squared > num:
                right = x - 1
            else:
                left = x + 1

        return False

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1: return True
        l,r = 2,num//2
        while l<=r:
            x = l + (r-l) //2
            guess = x * x
            if guess == num:
                return True
            if guess > num:
                r = x - 1
            else:
                l = x + 1
        return False